//
//  BalanceBST.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/3.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  1382. 将二叉搜索树变平衡     tag:二叉搜索树

import UIKit

/*
 1382. 将二叉搜索树变平衡
 给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。

 如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。

 如果有多种构造方法，请你返回任意一种。

  

 示例：
    1
      ↘
        2
          ↘
            3
              ↘
                4
 
 平衡后：
        2
      ↙   ↘
    1       3
              ↘
                4

 输入：root = [1,null,2,null,3,null,4,null,null]
 输出：[2,1,3,null,null,null,4]
 解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
  

 提示：

 树节点的数目在 1 到 10^4 之间。
 树节点的值互不相同，且在 1 到 10^5 之间。
 */


class BalanceBST: NSObject {
    
    var treeArr:[Int] = []
    
    //原二叉树已经是一个二叉查找树 因此对一个二叉查找树进行中序遍历即可得到一个有序的升序数组，对这个数组重新构造平衡的二叉查找树即可
    func balanceBST(_ root: TreeNode?) -> TreeNode? {
        self.traverseTree(root)
        print("\(treeArr)")
        return self.helper(treeArr, 0, treeArr.count - 1)
    }
    
    func helper(_ nums:[Int], _ left:Int, _ right:Int) -> TreeNode?{
        if left > right {
            return nil
        }
        
        let mid = (left+right)/2
        let rootNode = TreeNode(nums[mid])
        rootNode.left = self.helper(nums, left, mid - 1)
        rootNode.right = self.helper(nums, mid + 1, right)
        return rootNode
    }
    
    
    //中序遍历二叉树
    func traverseTree(_ rootNode:TreeNode?){
        guard rootNode != nil else{
            return
        }
        self.traverseTree(rootNode!.left)
        //print(rootNode!.val)
        treeArr.append(rootNode!.val)
        self.traverseTree(rootNode!.right)
    }
    
    //满遍历
//    func fullTraverseTree(_ rootNode:TreeNode?){
//        if rootNode == nil {
//
//            treeArr.append(999)
//        }else{
//            treeArr.append(rootNode!.val)
//            self.fullTraverseTree(rootNode!.left)
//            self.fullTraverseTree(rootNode!.right)
//
//        }
//    }
    
    func levelTraverseTree(){
        
    }

}
